package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-path-sum/description/
 * @create 2025/8/28 10:12
 * @since JDK17
 */

public class Solution16 {
    int m, n;
    static int[][] dp = new int[201][201];

    public int f(int[][] grid, int x, int y) {
        if (x == n - 1 && y == m - 1) {
            return grid[x][y];
        }
        if (dp[x][y] != -1) {
            return dp[x][y];
        }
        int down = Integer.MAX_VALUE, right = Integer.MAX_VALUE;
        if (x < n - 1) {
            down = grid[x][y] + f(grid, x + 1, y);
        }
        if (y < m - 1) {
            right = grid[x][y] + f(grid, x, y + 1);
        }
        return dp[x][y] = Math.min(down, right);
    }
    public int f2(int[][] grid, int x, int y) {
        int n = grid.length, m = grid[0].length;
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[0][i] = grid[0][i] + dp[0][i - 1];
        }
        for (int i = 1; i < n; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[n - 1][m - 1];
    }
    public int minPathSum(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], 0, m, -1);
        }
        return f(grid, 0, 0);
    }
}
